class AnimalShelf
{
public:
    AnimalShelf()
    {
    }

    void enqueue(vector<int> animal)
    {
        if (animal[1] == 0)
        {
            catQueue.push({animal[0], i});
        }
        else
        {
            dogQueue.push({animal[0], i});
        }
        ++i;
    }

    vector<int> dequeueAny()
    {
        if (!catQueue.empty() && !dogQueue.empty())
        {
            if (catQueue.front().second < dogQueue.front().second)
            {
                int catId = catQueue.front().first;
                catQueue.pop();
                return {catId, 0};
            }
            else
            {
                int dogId = dogQueue.front().first;
                dogQueue.pop();
                return {dogId, 1};
            }
        }
        if (!catQueue.empty())
        {
            int catId = catQueue.front().first;
            catQueue.pop();
            return {catId, 0};
        }
        if (!dogQueue.empty())
        {
            int dogId = dogQueue.front().first;
            dogQueue.pop();
            return {dogId, 1};
        }
        return {-1, -1};
    }

    vector<int> dequeueDog()
    {
        if (!dogQueue.empty())
        {
            int dogId = dogQueue.front().first;
            dogQueue.pop();
            return {dogId, 1};
        }
        return {-1, -1};
    }

    vector<int> dequeueCat()
    {
        if (!catQueue.empty())
        {
            int catId = catQueue.front().first;
            catQueue.pop();
            return {catId, 0};
        }
        return {-1, -1};
    }

private:
    int i = 0;
    queue<pair<int, int>> catQueue;
    queue<pair<int, int>> dogQueue;
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */